package com.example.question.bt.backtrack1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Date 2023-07-16
 * @Author Jonathan
 * @link {<a href="https://leetcode.cn/problems/letter-combinations-of-a-phone-number/">...</a>}
 */
public class Code09_17 {

    private Map<Character, String> phone = new HashMap<Character, String>() {{
        put('2', "abc");
        put('3', "def");
        put('4', "ghi");
        put('5', "jkl");
        put('6', "mno");
        put('7', "pqrs");
        put('8', "tuv");
        put('9', "wxyz");
    }};


    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits == null || digits.isEmpty()) {
            return res;
        }
        dfs(digits, 0, "", res);
        return res;
    }


    /**
     * toString()非常的耗费性能
     * StringBuilder的性能比String好
     *
     * @param digits
     * @param index
     * @param paths
     * @param res
     */
    private void dfs(String digits, int index, String paths, List<String> res) {
        if (index == digits.length()) {
            res.add(paths);
            return;
        }
        char c = digits.charAt(index);
        char[] chars = phone.get(c).toCharArray();
        for (char aChar : chars) {
            dfs(digits, index + 1, paths + aChar, res);
        }
    }

    private void dfs1(String digits, int index, StringBuilder paths, List<String> res) {
        if (index == digits.length()) {
            res.add(paths.toString());
            return;
        }
        char c = digits.charAt(index);
        char[] chars = phone.get(c).toCharArray();
        for (char aChar : chars) {
            paths.append(aChar);
            index += 1;
            dfs1(digits, index, paths, res);
            index -= 1;
            paths.deleteCharAt(paths.length() - 1);// 删除最后一个 还原现场
        }
    }
}
